package leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author Retain
 * @date 2021/8/15 14:27
 */
public class FindK {

      static class ListNode {
        int val;
        ListNode next = null;
        public ListNode(int val) {
          this.val = val;
        }
      }

    public int findK (int[] array, int n, int k) {
        // write code here
        PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> o2 - o1);

        for (int i = 0; i < n; i++) {
            heap.offer(array[i]);
        }
        while (k > 1) {
            heap.poll();
            k--;
        }
        return heap.poll();
    }

    public static void main(String[] args) {
    List<Integer> list = new ArrayList<>();
    int[] s = list.stream().mapToInt(Integer::intValue).toArray();

//        FindK findK = new FindK();
//        ListNode node1 = new ListNode(1);
//        ListNode node2 = new ListNode(2);
//        ListNode node3 = new ListNode(3);
//        ListNode node4 = new ListNode(4);
//        ListNode node5 = new ListNode(5);
//        node1.next = node2;
//        node2.next = node3;
//        node3.next = node4;
//        node4.next = node5;
//
//        ListNode listNode = findK.reverseKGroup(node1, 2);
//        System.out.println();
    }
    public ListNode reverseKGroup (ListNode list, int k) {
        // write code here
        if (list == null || list.next == null) {
            return null;
        }
        // 哨兵结点头节点
        ListNode dummy = new ListNode(0);

        dummy.next = list;

        // pre: 上一组结点的尾结点，tail：每次翻转链表的尾结点
        ListNode prev = dummy;
        ListNode tail = dummy;

        while (tail.next != null) {
            // 循环k次，找到需要翻转链表结尾
            for (int i = 0; i < k; i++) {
                if (tail != null) {
                    tail = tail.next;
                }
            }
            // 判断tail是否为null，null则直接跳过
            if (tail == null) {
                break;
            }
            // 下一组翻转的头节点
            ListNode next = tail.next;
            // 断开链表
            tail.next = null;
            // 记录翻转的头节点,dummy.next,即head
            ListNode start = prev.next;
            prev.next = reverse(start);
            // 翻转后头节点到最后,重新链接
            start.next = next;
            prev = start;
            // 将tail置为下一次翻转链表头节点的上一个结点，即start
            tail = start;
        }
        // 返回新链表
        return dummy.next;

    }

    /**
     *  翻转链表
     */
    private ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 前一个结点
        ListNode prev = null;
        // 当前结点
        ListNode cur = head;
        // 下一个结点
        ListNode next;
        // 翻转
        while (cur != null) {
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        // 翻转后prev为新头节点
        return prev;
    }
}
